﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace LeetCodeSolutions
{
    /// <summary>
    /// LeetCode题库21 合并有序链表
    /// </summary>
    class LeetCode21: LeetCodeBase
    {
        public override void Execute()
        {
            LeetCode21.ListNode node1 = new LeetCode21.ListNode(1);
            LeetCode21.ListNode node2 = new LeetCode21.ListNode(2);

            LeetCode21.ListNode node11 = new LeetCode21.ListNode(11);
            LeetCode21.ListNode node22 = new LeetCode21.ListNode(22);

            LeetCode21.ListNode node111 = new LeetCode21.ListNode(111);
            LeetCode21.ListNode node222 = new LeetCode21.ListNode(222);

            LeetCode21.ListNode node1111 = new LeetCode21.ListNode(1111);

            node1.next = node11;
            node11.next = node111;
            node111.next = node1111;

            node2.next = node22;
            node22.next = node222;

            MergeTwoLists(node1, node2);
        }

        public class ListNode
        {
            public int val;
            public ListNode next;
            public ListNode(int val = 0, ListNode next = null)
            {
                this.val = val;
                this.next = next;
            }
        }

        public ListNode MergeTwoLists(ListNode l1, ListNode l2)
        {
            if(l1 == null && l2 == null)
            {
                return null;
            }

            if (l1 == null || l2 == null)
            {
                return l1 == null ? l2 : l1;
            }

            var list1 = ListNode2List(l1);
            var list2 = ListNode2List(l2);
            list1.AddRange(list2);
            list1.Sort();

            CommonFuntions.Print("l1 " + list1.Count + " l2 " + list2.Count);

            List<ListNode> listNodesList = new List<ListNode>();
            for (int i = 0; i < list1.Count; i++)
            {
                listNodesList.Add(new ListNode(list1[i]));
            }
            for (int i = 0; i < list1.Count - 1; i++)
            {
                listNodesList[i].next = listNodesList[i + 1];
            }

            return listNodesList[0];
        }

        private List<int> ListNode2List(ListNode node)
        {
            if (node == null)
            {
                return null;
            }

            List<int> list = new List<int>();
            while (node != null)
            {
                list.Add(node.val);
                node = node.next;
            }

            return list;
        }
    }
}